import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
* @description: 886. 可能的二分法
* @author hewei
* @date 2022/9/15 14:18
* @version 1.0
*/

public class PossibleBipartition {

    HashMap<Integer, List<Integer>> map;
    int[] color;
    public boolean possibleBipartition(int n, int[][] dislikes) {
        if (dislikes.length == 0) return true;
        color = new int[n + 1];
        map = new HashMap<>();
        for (int[] dislike : dislikes) {
            if (!map.containsKey(dislike[0])) map.put(dislike[0], new ArrayList<>());
            if (!map.containsKey(dislike[1])) map.put(dislike[1], new ArrayList<>());
            map.get(dislike[0]).add(dislike[1]);
            map.get(dislike[1]).add(dislike[0]);
        }
        for (int i = 1; i < n + 1; i++) {
            if (color[i] == 0 && !process(i, -1)) return false;
        }
        return true;
    }

    public boolean process(int target, int temp) {
        if (color[target] != 0) return color[target] == temp;
        color[target] = temp;

        if (map.containsKey(target))
        for (Integer i : map.get(target)) {
            if (!process(i, -temp)) return false;
        }
        return true;
    }
}
